package 题组;

/**
 * @author 挚爱之夕
 * @date 2021/9/7 - 09 - 07 - 12:15
 * @Description: 题组
 * @Version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] coins = new int[]{83,186,408,419};
        int amount = 6249;
        int ans = new Solution().coinChange(coins,amount);
        System.out.println(ans);
    }
    public int coinChange(int[] coins, int amount) {
        int sum = 0;
        int kind = coins.length-1;
        int count ;
        while(amount>0){
            if(kind<0)
                break;
            count = amount /coins[kind];
            amount -= count * coins[kind];
            kind --;
            sum += count;
        }
        if(!(amount>0))
            return sum;
        else
            return -1;
    }
}
